package q207_canFinish;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Solution_1 {
    /*
    用BFS的方式来解决拓扑图的问题
    如何修完所有课程？我们考虑构建一个有向无环图（如果有环代表一定无法修完所有课）
    我们以[3 0] [3 1] [4 1] [4 2] [5 3] [5 4]为例
    其代表 先上了0和1 才能够上3 先上了1和2 才能够上4 先上了3和4 才能够上5
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses]; // 入度表
        List<List<Integer>> adjTable = new ArrayList<>();  // 邻接表
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            // 构建对应数量的邻接表 有多少门课 就有多少个邻接表
            adjTable.add(new ArrayList<>());
        }
        for (int[] pre : prerequisites) {
            /*
            考虑入度表是什么样的
            我们以上面的例子作为参考 首先[3 0]中代表要先上0 再上3 所以首先是inDegree[3]++
            代表3这个位置的度变成1 实际上课程已经指定记为 0 到 numCourses - 1 所以可以用数组来计算。

            然后再读取到[3 1]时 3的位置度就变成2了 以此类推 4和5的度都是2
            对于adjTable 则对于0的位置有一个邻接表{3} 对于1则是{3, 4}...
             */
            inDegree[pre[0]]++;
            adjTable.get(pre[1]).add(pre[0]);
        }
        // 接下来将所有度为0的都放到队列里面
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        // 开始统计能够上多少课
        int index = 0;

        while (!queue.isEmpty()) {
            /*
            首先对于所有的度为0的课都是可以直接上的
            所以可以index++
             */
            int temp = queue.poll();
            index++;
            for (int cour : adjTable.get(temp)) {
                // 然后考虑邻接表 例如0这门课的邻接表是{3} 导致3的入度--
                // 之后读取到1的课程的时候 3和4的入度也会减1 如果发现了度为0的课 就继续加入到队列中
                inDegree[cour]--;
                if (inDegree[cour] == 0) {
                    queue.add(cour);
                }
            }
        }
        // 最后看能不能上完所有课
        return index == numCourses;
    }

}
